/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
#include <vector>
class Solution {
public:
	vector<TreeNode*> ret;
	void order_vist(TreeNode* root)
	{
		if(root == nullptr)
		{
			return;
		}
		order_vist(root->left);
		ret.push_back(root);
		order_vist(root->right);
	}
    TreeNode* Convert(TreeNode* root) {
		order_vist(root);   
		//这样在ret中储存的就是排序好的二叉树节点了
		if(ret.size() == 0)
		{
			return nullptr;
		}
		TreeNode* newhead = ret[0];
		TreeNode* cur = newhead;
		for(int i = 1;i<ret.size();i++)
		{
			TreeNode* tmp = ret[i];
			cur->right = tmp;
			tmp->left = cur;
			cur = cur->right;
		}
		return newhead;
    }
};
